1. Field of the Invention
This invention relates generally to computer graphics. More particularly, the present invention relates to a method for determining whether a distant object is completely obstructed by a closer object, for use in real-time 3-dimensional graphics.
2. Description of the Related Art
By about 1950, computer scientists working in graphics could produce, on a computer screen, a moving blip that simulated a bouncing ball. But with the increases in computer memory and speed achieved since then, graphics programmers have raised their visualizing standards vastly higher. Today they seek realism, not just for static images but for animated ones as well. Such realism, however, is difficult to achieve in real-time 3-dimensional graphics because of the numerous computations needed, in a short period of time, to make an animated 3-dimensional object move realistically in real-time.
Computer graphics may be considered as having two fundamentals: modeling, and rendering. In modeling, an artist or a designer essentially builds a mathematical model of an object, by introducing all the structural information, such as which points are to be joined by lines or curves, or where a sphere attaches to a cube, or how an image can be approximated by triangles. Abstract information, for example, how a scene might change in response to different lighting, must also be provided for. In rendering, the computer is made to display the model's final colors, textures, highlights, shadows, and so forth, on the screen, at the new position of the object.
When an object is static or stationary, for example, if the view point is constrained to follow a specific path and most objects do not move, the necessary calculations can be made, and the resulting data stored, long before the computer video game is played. When the game is actually played, previously stored information is used to generate the static image. The amount of time needed to make the calculations does not matter, because the calculations do not need to be made while the game is being played.
In the case of a computer video game where the view point is less constrained or there are a large number of moving objects, new position information must be determined as the game is played. For example, in a sophisticated flight simulator program, the position of an aircraft, or of an object approached by an aircraft, might need to be changed in real-time.
In a sophisticated computer video game, the field-of-view, that is, the 3-dimensional area of play as seen by the player, might include numerous 3-dimensional objects. For example, in a flight simulator program, the field-of-view might include numerous buildings and trees, aircraft, boats and other vessels, missiles, and debris. A particular object, for example an airplane, might be within the player's field-of-view at one time, but not at another, because it becomes obstructed by one of the buildings, either because the airplane being observed has moved or because the player has moved, or both. In known prior art computer graphics, the numerous calculations to determine the object's new position, shape, and appearance are made, and based on those results, the object is drawn pixel by pixel into a display memory. In some cases, a test might be made on each pixel to determine whether it is obscured by a pixel generated from a closer object. In other cases, the memory is over-written by pixel information for closer objects. Numerous calculations are made even when the object is totally obstructed from view by a closer object, thereby wasting valuable real-time computation time, because not until the calculations are made to render the object does it become known that the object is obstructed from view.
The present invention provides a quick, efficient method for determining whether a distant object is completely obstructed from view by a closer object. If it is totally obstructed from view, then the distant object can be discarded and no further calculations need to be made to render that object, thereby saving valuable real-time computation time; if, on the other hand, it can not be determined whether the distant object is completely obstructed from view by the closer object, then calculations can proceed in the normal manner to render that object. Thus the present invention is directed to overcoming, or at least reducing, the effects of one or more of the problems mentioned above.